from typing import List


# 某个元素超过一半
class Solution:
    def majorityElement(self, nums: List[int]):
        if len(nums) < 2:
            return nums[0]
        candidate = nums[0]
        count = 1
        for i in range(1, len(nums)):
            if nums[i] == candidate:
                count += 1
            else:
                count -= 1
            if count < 0:
                candidate = nums[i]
                count = 1
        if nums.count(candidate) > len(nums)//2:
            return candidate


# 某两个元素超过 n/3
class Solution1:
    def majorityElement(self, nums: List[int]) -> List[int]:
        result = []
        if len(nums) < 1:
            return result
        candidate1, candidate2 = nums[0], nums[0]
        count1, count2 = 0, 0
        for i in range(len(nums)):
            if nums[i] == candidate1:
                count1 += 1
                continue
            if nums[i] == candidate2:
                count2 += 1
                continue

            if count1 == 0:
                candidate1 = nums[i]
                count1 += 1
                continue
            if count2 == 0:
                candidate2 = nums[i]
                count2 += 1
                continue

            count1 -= 1
            count2 -= 1
        count1, count2 = 0, 0
        for j in range(len(nums)):
            if candidate1 == nums[j]:
                count1 += 1
            if candidate2 == nums[j]:
                count2 += 1
        if count1 > len(nums)/3:
            result.append(candidate1)
        if count2 > len(nums)/3 and candidate2 != candidate1:
            result.append(candidate2)
        return result


if __name__ == '__main__':
    t = [1]
    x = Solution1()
    print(x.majorityElement(t))
